UVa/11509 - Touring Robot/trobot.cpp

   1 /*
   2 Accepted
   3 */
   4 #include<iostream>
   5 #include<stdio.h>
   6 #include<math.h>
   7 #include<vector>
   8 using namespace std;
   9 #define D(x) cout<<__LINE__ <<": " <<#x<<" es "<<x<<endl
  10
  11 const double pi = acos(-1.0);
  12
  13 inline double toGrad(double a){ return 180*a / pi; }
  14
  15 struct point{
  16   double x, y;
  17   point(){} point(double x, double y) : x(x), y(y) {}
  18   const point operator-(const point &that) const{
  19     return point(this->x - that.x, this->y - that.y);
  20   }
  21   void print() const{printf("%lf %lf, inclination = %lf\n", x, y, toGrad(atan2(y, x)));}
  22 };
  23
  24 /*
  25 Retorna el ángulo de inclinación del vector p, barrido
  26 en sentido antihorario a partir del eje X positivo.
  27 0 <= angulo <= 2*pi
  28 */
  29 double ccw(point p){
  30   double r = atan2(p.y, p.x);
  31   if (r < 0.0) r += 2*pi;
  32   return r;
  33 }
  34
  35 double rotation(point a, point b, point c){
  36   //D(  asin(((b.x-a.x)*(c.y-b.y)-(b.y-a.y)*(c.x-b.x))/(hypot(b.x-a.x,b.y-a.y)*hypot(c.x-b.x,c.y-b.y)))*180.0/pi);
  37   double antes = ccw(b-a), despues = ccw(c-b);
  38   double giro = 0.0;
  39   if (despues > antes) giro = despues - antes;
  40   else if (antes > despues) giro = 2*pi - (antes - despues);
  41   //  a.print(),b.print(),c.print(), D(giro);
  42   return giro;
  43 }
  44
  45
  46
  47 int main(){
  48   //assert(freopen("trobot.in", "r", stdin) != NULL);
  49   int n;
  50   while (cin >> n && n){
  51     vector<point> p(n);
  52     for(int i=0;i<n && scanf("%lf%lf",&p[i].x,&p[i].y)!=EOF;++i);
  53     double ans=0.0;
  54     for(int i=0; i<n ;++i)ans+=rotation(p[i],p[(i+1)%n],p[(i+2)%n]);//, D(ans);
  55     printf("%.0lf\n",ans/(2*pi));
  56   }
  57   return 0;
  58 }